package net.cyndeline.rlgraph.embedding.mutable

import net.cyndeline.rlgraph.embedding.{AdjacencyEntry, AdjacencyList}
import scala.collection.mutable.ArrayBuffer
import scala.collection.mutable

/**
 * A collection of common operations for adjacency entries. Stores a doubly linked
 * list of entries as they are embedded around a vertex.
 *
 * @tparam VType The type of nodes that are embedded in the list.
 * @param vertex The vertex that this adjacency list has been assigned to.
 * @param head The first entry in the list.
 */
class DoublyLinkedList[VType](val vertex: VType, val head: DoublyLinkedEntry[VType]) extends AdjacencyList[VType] {
  private val vertices = new mutable.HashSet[VType]()
  private val entries: List[DoublyLinkedEntry[VType]] = setup(head)

  /**
   * @return an iterator over all adjacency entries in the order they are embedded.
   */
  override def iterator: Iterator[AdjacencyEntry[VType]] = entries.iterator

  /**
   * @return the number of entries in the list.
   */
  override def size: Int = entries.size

  /**
   * Fetches an entry containing a specific vertex. Does not guarantee constant lookup time, and
   * throws a NoSuchElementException if the vertex is not present.
   * @param vertex A vertex embedded in the list.
   * @return the entry storing the specified vertex.
   */
  override def entryFor(vertex: VType): AdjacencyEntry[VType] = {
    val it = iterator
    while(it.hasNext) {
      val entry = it.next()
      if (entry.vertex == vertex) return entry
    }

    throw new NoSuchElementException("The vertex " + vertex + " was not found in the list.")
  }

  /**
   * @param vertex The vertex to look for.
   * @return True if this adjacency list contains an embedding for the specified vertex, otherwise false.
   */
  override def containsEntryFor(vertex: VType): Boolean = vertices.contains(vertex)

  /**
   * @return a list of all vertices in the order they are embedded.
   */
  override def toList: List[AdjacencyEntry[VType]] = entries

  override def toString(): String = entries.toString()

  private def setup(head: DoublyLinkedEntry[VType]): List[DoublyLinkedEntry[VType]] = {
    var current = head
    val allEntries = new ArrayBuffer[DoublyLinkedEntry[VType]]()
    do {
      vertices += current.vertex
      allEntries += current
      current = current.nextEntry
    } while(current.vertex != head.vertex)

    allEntries.toList
  }
}
